Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
Identifieur interne : 004C65 ( Main/Exploration ); précédent : 004C64; suivant : 004C66Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
Auteurs : Mohamed Ali Aloulou [France] ; Mikhail Y. Kovalyov [Biélorussie] ; Marie-Claude Portmann [France]Source :
- RAIRO - Operations Research [ 0399-0559 ] ; 2007-06-15.
English descriptors
- mix :
Abstract
We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined by a partial order of jobs and a type of the schedules. In this paper, the schedules of active and non-delay type are considered. A flexible solution can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance of a flexible solution includes the best case and the worst case performances. The best case performance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule of the set of schedules characterizing the flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following the given structure in the on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimum and maximum values of the considered objective function, respectively. We present algorithmic and computational complexity results for some maximization scheduling problems. In these problems, the jobs to be scheduled have different release dates and precedence constraints may be given on the set of jobs.
Url:
DOI: 10.1051/ro:20070012
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003459
- to stream Istex, to step Curation: 003417
- to stream Istex, to step Checkpoint: 001050
- to stream Hal, to step Corpus: 002034
- to stream Hal, to step Curation: 002034
- to stream Hal, to step Checkpoint: 003D69
- to stream Main, to step Merge: 004D99
- to stream Main, to step Curation: 004C65
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity</title><author><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name></author><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name></author><author><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:DC722999C8D60D14DE7E225EC7E9DBD8962B28CA</idno><date when="2007" year="2007">2007</date><idno type="doi">10.1051/ro:20070012</idno><idno type="url">https://api.istex.fr/ark:/67375/80W-7QRK1N13-2/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003459</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003459</idno><idno type="wicri:Area/Istex/Curation">003417</idno><idno type="wicri:Area/Istex/Checkpoint">001050</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001050</idno><idno type="wicri:doubleKey">0399-0559:2007:Aloulou M:evaluating:flexible:solutions</idno><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00118734</idno><idno type="url">https://hal.inria.fr/inria-00118734</idno><idno type="wicri:Area/Hal/Corpus">002034</idno><idno type="wicri:Area/Hal/Curation">002034</idno><idno type="wicri:Area/Hal/Checkpoint">003D69</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003D69</idno><idno type="wicri:doubleKey">0399-0559:2007:Aloulou M:evaluating:flexible:solutions</idno><idno type="wicri:Area/Main/Merge">004D99</idno><idno type="wicri:Area/Main/Curation">004C65</idno><idno type="wicri:Area/Main/Exploration">004C65</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity </title><author><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name><affiliation wicri:level="3"><country wicri:rule="url">France</country><wicri:regionArea>LAMSADE – Université Paris Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Paris</settlement></placeName></affiliation></author><author><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name><affiliation wicri:level="1"><country wicri:rule="url">Biélorussie</country><wicri:regionArea>Faculty of Economics, Belarusian State University, and United Institute of Informatics Problems, National Academy of Sciences ofBelarus, Minsk</wicri:regionArea><wicri:noRegion>Minsk</wicri:noRegion></affiliation></author><author><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name><affiliation wicri:level="3"><country wicri:rule="url">France</country><wicri:regionArea>MACSI team of INRIA-Lorraine and LORIA-INPL, École des Mines de Nancy, Parc de Saurupt, 54042 Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j" type="main">RAIRO - Operations Research</title><title level="j" type="abbrev">RAIRO-Oper. Res.</title><title level="j" type="publisher-id">ro</title><idno type="ISSN">0399-0559</idno><idno type="eISSN">1290-3868</idno><imprint><publisher>EDP Sciences</publisher><date type="Final-Published" when="2007-06-15">2007-06-15</date><date type="Published" when="2007-01">2007-01</date><date type="ePublished" when="2007-06-15">2007-06-15</date><date type="Published" when="2007-06-15">2007-06-15</date><biblScope unit="vol">41</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="1">1</biblScope><biblScope unit="page" to="18">18</biblScope><biblScope unit="page-count">18</biblScope></imprint><idno type="ISSN">0399-0559</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0399-0559</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>active and non-delay schedules</term><term>maximization problems</term><term>schedule flexibility</term><term>scheduling</term><term>single machine</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined by a partial order of jobs and a type of the schedules. In this paper, the schedules of active and non-delay type are considered. A flexible solution can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance of a flexible solution includes the best case and the worst case performances. The best case performance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule of the set of schedules characterizing the flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following the given structure in the on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimum and maximum values of the considered objective function, respectively. We present algorithmic and computational complexity results for some maximization scheduling problems. In these problems, the jobs to be scheduled have different release dates and precedence constraints may be given on the set of jobs.</div></front></TEI><affiliations><list><country><li>Biélorussie</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Île-de-France</li></region><settlement><li>Nancy</li><li>Paris</li></settlement></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Aloulou, Mohamed Ali" sort="Aloulou, Mohamed Ali" uniqKey="Aloulou M" first="Mohamed Ali" last="Aloulou">Mohamed Ali Aloulou</name></region><name sortKey="Portmann, Marie Claude" sort="Portmann, Marie Claude" uniqKey="Portmann M" first="Marie-Claude" last="Portmann">Marie-Claude Portmann</name></country><country name="Biélorussie"><noRegion><name sortKey="Kovalyov, Mikhail Y" sort="Kovalyov, Mikhail Y" uniqKey="Kovalyov M" first="Mikhail Y." last="Kovalyov">Mikhail Y. Kovalyov</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004C65 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004C65 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:DC722999C8D60D14DE7E225EC7E9DBD8962B28CA
|texte= Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity
}}
| This area was generated with Dilib version V0.6.33. |  |